How AI in Games Works

State Machines

So how does a gaming character give the impression of being intelligent? To answer that requires a little grounding in the basics of AI. Let’s start with the traditional first-person shooter enemies of yore, which idly patrol their area until they notice you and then start shooting at you. The decisions of these characters are made using state machines.

Each non-player character or squad of non-player characters has a number of states, such as ‘man shooting’ or ‘seeking enemy,’ and each of these states has various actions and behaviours associated with it. For example, a character in a ‘man shooting’ state has actions such as firing and reloading weapons, and the character then changes to another state if a certain number of criteria are met. If the enemy moves out of sight, the character might change to a ‘seeking enemy’ state and employ a set of actions that involve looking around the game world for new enemies.

This concept is simple enough, but the decision trees that make up state machines become massively more complicated as you make characters more intelligent. These decision trees feature a hierarchy of behaviours, and are therefore called hierarchical finite state machines (HFSMs).

Like a family tree, this starts with a single state (such as charge), which can then branch out to a behaviour (such as engage or retreat). Each of these behaviours will then have a number of sub-options (such as flee or guard), which can also branch out into even more actions. The sub-options will compete with each other for execution, and the winner will be decided by the parent behaviour, which makes its decision based on the sub-option’s weighting and relevance to the current situation.


Chris Jurney, a senior programmer for Relic, offered the example of the state machines in its RTS, Dawn of War 2, to illustrate this. "The AI for Dawn of War 2 has roughly three main layers: the computer player, the squad and the entity," says Jurney. "The squad and the entities are both hierarchal finite state machines, and we have roughly 20 states at the squad level and 20 at the entity level. The states at the squad level pretty much map directly to orders that can be issued by the user.

"For example, if you issue a capture order to a squad, the squad will enter the SquadStateCapture state," continues Jurney. "This state might find that it’s not close enough yet to capture the point, so it will sub-state to SquadStateMove. In this state, the formation movement system will kick in and start issuing Move orders to individual entities, and the entities receive these commands and enter the StateMove state. Inside that, paths are found, dynamics are applied and generally, the individuals try to look smart as they perform their orders."
Some states will also be shared among multiple character types where relevant, and most characters spend most of their time using just a few standard states, with the others waiting in the wings for extraordinary circumstances.

Crytek’s Matthew Jack provides the example of the North Korean soldiers in Crysis, which he says have around 25 states from which to choose, but their "core behaviour is defined by only a small number of these". Jack estimates that "perhaps 90 per cent of their time is spent in only five states", while the other states "handle specific circumstances such as using or reacting to vehicles, using special weapons and so on".

State machines have been the staple core of gaming AI for decades, but they can only go so far before they get out of hand. A non-player character can have scripted or partly random behaviour, but using a state machine will mean that it’s inherently predictable to a certain degree. If you want to make a character appear more sophisticated, you need to make its state machines increasingly bigger – until they reach the point where they become unmanageable.

Creative Assembly’s studio communications manager, Kieran Brigden, explains, "When you start talking about an ever-expanding number of states then you start to run into problems. For example, if you have a huge number of states for a man in Empire: Total War, you then put 160 men in a unit, and 20 units in an army, think how many decision trees you’re having to do for every single man on the screen. We’re talking about several thousands of guys on the screen at one time; each of those has a massive state-based logic tree, so never mind your two percent processor overhead."

Crytek’s Matthew Jack concurs, saying that "the problem with state machines is defining all the transitions between them; 25 states isn’t such a big number for an AI character, but it can be hard for a developer to manage all the ways that a state might be reached, and ensure that it can be reached where it’s needed". Without revealing any specifics, Jack also adds that "since Crysis, we’ve moved towards other behaviour models to help us manage that complexity".